﻿#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct item{
	int a;
}Item;
typedef struct node{
	Item item;
	struct node * down;
	struct node * up;
}Node;
typedef Node * List;
void Add(List * plist, Item item) {
	Node * temp = *plist;
	Node * newnode = (Node*)malloc(sizeof(node));
	newnode->item = item;
	if ((*temp).item.a>item.a){
		newnode->down = temp;
		*plist = newnode;
	}
	else{
		while (temp->down != NULL&&(*temp->down).item.a<=item.a)
			temp = temp->down;
		if (temp->down!=NULL){
			newnode->down = temp->down;
			temp->down = newnode;
		}
		else if (temp->down==NULL){
			temp->down = newnode;
			newnode->down = NULL;
		}
	}
}
void Traverse(const List * plist) {
	Node * temp = *plist;
	while (temp!=NULL){
		printf("%d   ", temp->item.a);
		temp = temp->down;
	}
}
void EmptyTheList(List * plist) {
	Node* pfree;
	while (*plist != NULL) {
		pfree = (*plist)->down;
		free(*plist);
		(*plist) = pfree;
	}
}
int main() {
	srand(time(NULL));
	List * plist = NULL;
	for (size_t i = 0; i < 10000; i++){
		int randnum;
		randnum = rand();
		Item item;
		item.a = randnum;
		if (plist==NULL){
			Node * newnode = (Node*)malloc(sizeof(node));
			newnode->item = item;
			newnode->down = NULL;
			plist = &newnode;
		}
		else 
			Add(plist, item);
	}
	Traverse(plist);
	printf("done");
	EmptyTheList(plist);
	system("pause");
	return 0;
}